package com.arithmeticEveryDay._09_sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Sort {

    // 一、插入排序
    // 1、直接插入排序：每次往后找一个元素插入到前面已排好的有序部分
    public static <T extends Comparable<? super T>> T[] insertSort(T[] arr) {
        for (int i = 1; i < arr.length; i++) {
            // 记住要插入的元素值
            T temp = arr[i];
            int j;
            // 从i-1索引开始往后移出一个空位
            for (j = i - 1; j >= 0 && temp.compareTo(arr[j]) < 0; j--) {
                arr[j + 1] = arr[j];
            }
            // 插入到让出的空位中
            arr[j + 1] = temp;
        }
        return arr;
    }

    // 2、希尔排序：分组后直接插入
    public static <T extends Comparable<? super T>> T[] shellSort(T[] arr) {
        // 分成delta组
        for (int delta = arr.length / 2; delta > 0; delta /= 2) {
            // 直接插入排序
            for (int i = delta; i < arr.length; i++) {
                T temp = arr[i];
                int j;
                for (j = i - delta; j >= 0 && temp.compareTo(arr[j]) < 0; j -= delta) {
                    arr[j + delta] = arr[j];
                }
                arr[j + delta] = temp;
                // System.out.println(Arrays.toString(arr) + delta + ", " + i + ", " + (j+delta));
            }
        }
        return arr;
    }

    // 二、交换排序
    // 1、冒泡排序：相邻元素比较，不断交换使得数组有序
    public static <T extends Comparable<? super T>> T[] bubbleSort(T[] arr) {
        // n个数需要交换n-1轮数
        for (int i = 0; i < arr.length - 1; i++) {
            // 每交换一轮确定一个最值，因此-i，该部分不需要再考虑
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j].compareTo(arr[j + 1]) > 0) {
                    T temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        return arr;
    }

    // 2、快速排序：选定一个基准数，小于基准数的放在基准数前面，大于的放在其后面，然后分治解决
    public static <T extends Comparable<? super T>> T[] quickSort(T[] arr) {
        quickSort(arr, 0, arr.length - 1);
        return arr;
    }

    private static <T extends Comparable<? super T>> void quickSort(T[] arr, int begin, int end) {
        // TODO Auto-generated method stub
        /*
        if (begin >= 0 && begin < end && end < arr.length) {
            int left = begin;
            int right = end;
            // System.out.println(left + "/" + right); //
            System.out.println(Arrays.toString(arr));
            while (left != right) {
                while (left < right && arr[left].compareTo(arr[right]) < 0) {
                    right--;
                }
                if (left < right) {
                    T temp1 = arr[left];
                    arr[left] = arr[right];
                    arr[right] = temp1;
                    left++;
                }
                // System.out.println(left + ", " + right);
                while (left < right && arr[left].compareTo(arr[right]) < 0) {
                    left++;
                }
                if (left < right) {
                    T temp2 = arr[left];
                    arr[left] = arr[right];
                    arr[right] = temp2;
                    right--;
                }
            }
            if (right - 1 >= begin) {
                quickSort(arr, begin, right - 1);
            }
            if (left + 1 <= end) {
                quickSort(arr, left + 1, end);
            }
        }
        */

        if (begin >= 0 && begin < end && end < arr.length) {
            int left = begin;
            int right = end;
            T baseNum = arr[left];
            while (left != right) {
                while (left < right && arr[right].compareTo(baseNum) <= 0) {
                    right--;
                }
                if (left < right) {
                    arr[left] = arr[right];
                    left++;
                }
                while (left < right && arr[left].compareTo(baseNum) >= 0) {
                    left++;
                }
                if (left < right) {
                    arr[right] = arr[left];
                    right--;
                }
            }
            arr[left] = baseNum;
            quickSort(arr, begin, right - 1);
            quickSort(arr, left + 1, end);
        }

    }

    // 三、选择排序
    // 1、直接选择排序
    public static <T extends Comparable<? super T>> T[] selectSort(T[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int minIndex = i;
            for (int j = i; j < arr.length; j++) {
                if (arr[j].compareTo(arr[minIndex]) < 0) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                T temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
        return arr;
    }

    // 2、堆排序
    public static <T extends Comparable<? super T>> T[] heapSort(T[] arr) {

        return arr;
    }

    // 四、归并排序：相邻元素两两一组排序，然后归并为四四一组排序...直到所有元素归并为一组进行排序
    /*
    public static <T extends Comparable<? super T>> T[] mergeSort(T[] arr) {
        for (int length = 2; length / 2 <= arr.length; length *= 2) {
            for (int i = 0; i < arr.length; i += length) {
                // System.out.println(i);
                List<T> leftArr = new ArrayList<T>(length / 2);
                List<T> rightArr = new ArrayList<T>(length / 2);
                for (int j = i; j < i + length / 2 && j < arr.length; j++) {
                    leftArr.add(arr[j]);
                }
                for (int j = i + length / 2; j < i + length && j < arr.length; j++) {
                    rightArr.add(arr[j]);
                }
                // System.out.println(leftArr.toString());
                // System.out.println(rightArr.toString());
                int index = i;
                int leftIndex = 0;
                int rightIndex = 0;
                while (index < i + length && index < arr.length) {
                    while (leftIndex >= leftArr.size() && index < i + length && index < arr.length) {
                        arr[index++] = rightArr.get(rightIndex++);
                    }
                    while (rightIndex >= rightArr.size() && index < i + length && index < arr.length) {
                        arr[index++] = leftArr.get(leftIndex++);
                    }
                    if (leftIndex < leftArr.size() && rightIndex < rightArr.size() && index < i + length
                            && index < arr.length) {
                        if (leftArr.get(leftIndex).compareTo(rightArr.get(rightIndex)) < 0) {
                            arr[index++] = leftArr.get(leftIndex++);
                        } else {
                            arr[index++] = rightArr.get(rightIndex++);
                        }
                    } else {
                        break;
                    }
                }
                // System.out.println(Arrays.toString(arr));
            }
        }
        return arr;
    }
    */
    public static int[] mergeSort(int[] x) {
        int[] y = new int[x.length];
        int n = 1;
        while (n < x.length) {
            // 一趟归并，将x中若干相邻子序列归并到y中
            mergePass(x, y, n);
            // 子序列长度加倍
            n *= 2;
            System.out.println(n);
            System.out.println(Arrays.toString(x));
            System.out.println(Arrays.toString(y));
            if (n < x.length) {
                // 一趟归并，将y中若干相邻子序列再归并到x
                mergePass(y, x, n);
                n *= 2;
            }
            System.out.println(n);
            System.out.println(Arrays.toString(x));
            System.out.println(Arrays.toString(y));
        }
        return x;
    }
    
    // 一趟归并，将x中若干相邻子序列两两归并（升序）到y中，子序列长度为n
    private static void mergePass(int[] x, int[] y, int n) {
        // 将x中若干相邻子序列归并到y中
        for (int i = 0; i < x.length; i += 2*n) {
            // 一次归并
            merge(x, y, i, i+n, n);
        }
    }
    
    // 将x中分别以begin1、begin2开始的两个相邻子序列归并(升序)到y中，子序列长度为n
    private static <T extends Comparable<? super T>> void merge(int[] x, int[] y, int begin1, int begin2, int n) {
        int i = begin1, j = begin2, k = begin1;
        // 将x中两个相邻子序列归并到y中
        while (i < begin1 + n && j < begin2 + n && j < x.length) {
            // 将较小值复制到y中
            if (x[i] <= x[j]) {
                y[k++] = x[i++];
            } else {
                y[k++] = x[j++];
            }
        }
        // 将前一个子序列剩余元素复制到y序列，序列长度可能不足n
        while (i < begin1 + n && i < x.length) {
            y[k++] = x[i++];
        }
        // 将后一个子序列剩余元素复制到y中
        while (j < begin2 + n && j < x.length) {
            y[k++] = x[j++];
        }
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Integer[] arr3 = { 4, 1, 3, 7, 9, 6, 4, 2, 5, 8 };
        System.out.println("直接插入排序：" + Arrays.toString(insertSort(arr3)));
        Integer[] arr5 = { 4, 1, 3, 7, 9, 6, 4, 2, 5, 8 };
        System.out.println("希尔排序：" + Arrays.toString(shellSort(arr5)));
        Integer[] arr1 = { 4, 1, 3, 7, 9, 6, 4, 2, 5, 8 };
        System.out.println("冒泡排序：" + Arrays.toString(bubbleSort(arr1)));
        Integer[] arr4 = { 4, 1, 3, 7, 9, 6, 4, 2, 5, 8 };
        System.out.println("快速排序：" + Arrays.toString(quickSort(arr4)));
        Integer[] arr2 = { 4, 1, 3, 7, 9, 6, 4, 2, 5, 8 };
        System.out.println("直接选择排序：" + Arrays.toString(selectSort(arr2)));
        int[] arr6 = { 4, 1, 3, 7, 9, 6, 4, 2, 5, 8 };
        System.out.println("归并排序：" + Arrays.toString(mergeSort(arr6)));
    }

}

